In mathematics, a bounded sequence {s1, s2, s3, …} of real numbers is said to be equidistributed, or uniformly distributed, if the proportion of terms falling in a subinterval is proportional to the length of that interval. Such sequences are studied in Diophantine approximation theory and have applications to Monte Carlo integration.
Contents |
A bounded sequence {s1, s2, s3, …} of real numbers is said to be equidistributed on an interval [a, b] if for any subinterval [c, d] of [a, b] we have
(Here, the notation |{s1,…,sn }∩[c,d]| denotes the number of elements, out of the first n elements of the sequence, that are between c and d.)
For example, if a sequence is equidistributed in [0, 2], since the interval [0.5, 0.9] occupies 1/5 of the length of the interval [0, 2], as n becomes large, the proportion of the first n members of the sequence which fall between 0.5 and 0.9 must approach 1/5. Loosely speaking, one could say that each member of the sequence is equally likely to fall anywhere in its range. However, this is not to say that {sn} is a sequence of random variables; rather, it is a determinate sequence of real numbers.
We define the discrepancy D(N) for a sequence {s1, s2, s3, …} with respect to the interval [a, b] as
A sequence is thus equidistributed if the discrepancy D(N) tends to zero as N tends to infinity.
Equidistribution is a rather weak criterion to express the fact that a sequence fills the segment leaving no gaps. For example, the drawings of a random variable uniform over a segment will be equidistributed in the segment, but there will be large gaps compared to a sequence which first enumerates multiples of ε in the segment, for some small ε, in an appropriately chosen way, and then continues to do this for smaller and smaller values of ε. See low-discrepancy sequence for stronger criteria and constructions of low-discrepancy sequences for constructions of sequences which are more evenly distributed.
The sequence {a1, a2, a3, …} is said to be equidistributed modulo 1 or uniformly distributed modulo 1 if the sequence of the fractional parts of the an's, (denoted by an−⌊an⌋)
is equidistributed in the interval [0, 1].
is uniformly distributed modulo 1: this is the equidistribution theorem.
is equidistributed modulo 1. This is a famous theorem of analytic number theory, proved by I. M. Vinogradov in 1935.
The following three conditions are equivalent:
The third condition is known as Weyl's criterion. Together with the formula for the sum of a finite geometric series, the equivalence of the first and third conditions furnishes an immediate proof of the equidistribution theorem.
Metric theorems describe the behaviour of a parametrised sequence for almost all values of some parameter α: that is, for values of α not lying in some exceptional set of Lebesgue measure zero.
It is not known whether the sequences {en} or {πn} are equidistributed mod 1. However it is known that the sequence {αn} is not equidistributed mod 1 if α is a PV number.
A bounded sequence {s1, s2, s3, …} of real numbers is said to be well-distributed on [a, b] if for any subinterval [c, d] of [a, b] we have
uniformly in k. Clearly every well-distributed sequence is uniformly distributed, but the converse does not hold. The definition of well-distributed modulo 1 is analogous.